{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 线性数据结构\n",
    "\n",
    "## 什么是线性数据结构\n",
    "队列，栈，链表是一类数据的容器，它们数据项之间的顺序由添加或删除的顺序决定。一旦一个数据项被添加，它相对于前后元素一直保持该位置不变。诸如此类的数据结构被称为**线性数据结构**。\n",
    "\n",
    "线性数据结构有两端，有时被称为左右，某些情况被称为前后。你也可以称为顶部和底部，名字都不重要。将两个线性数据结构区分开的方法是添加和移除项的方式，特别是添加和移除项的位置。例如一些结构允许从一端添加项，另一些允许从另一端移除项。\n",
    "\n",
    "这些变种的形式产生了计算机科学最有用的数据结构。他们出现在各种算法中，并可以用于解决很多重要的问题。\n",
    "\n",
    "## 队列\n",
    "队列是项的有序结合，其中添加新项的一端称为队尾，移除项的一端称为队首。当一个元素从队尾进入队列时，一直向队首移动，直到它成为下一个需要移除的元素为止。\n",
    "\n",
    "最近添加的元素必须在队尾等待。集合中存活时间最长的元素在队首，这种排序成为 **FIFO(First In First Out)**，先进先出，也被称为先到先得。\n",
    "\n",
    "队列的最简单的例子非常多，排队等待电影，在杂货店的收营台等待，在自助餐厅排队等待（这样我们可以弹出托盘栈）。\n",
    "\n",
    "行为良好的线或队列是有限制的，因为它只有一条路，只有一条出路。不能插队，也不能离开。你只有等待了一定的时间才能到前面。下图展示了一个简单的 Python 对象队列。\n",
    "\n",
    "\n",
    "![](figures/3.10.figure1.png)\n",
    "\n",
    "\n",
    "计算机科学也有常见的队列示例。我们的计算机实验室有 30 台计算机与一台打印机联网。当学生想要打印时，他们的打印任务与正在等待的所有其他打印任务“一致”。第一个进入的任务是先完成。如果你是最后一个，你必须等待你前面的所有其他任务打印。我们将在后面更详细地探讨这个例子。\n",
    "\n",
    "除了打印队列，操作系统使用多个不同的队列来控制计算机内的进程。下一步做什么的调度通常基于尽可能快地执行程序和尽可能多的服务用户的排队算法。此外，当我们敲击键盘时，有时屏幕上出现的字符会延迟。这是由于计算机在那一刻做其他工作。按键的内容被放置在类似队列的缓冲器中，使得它们最终可以以正确的顺序显示在屏幕上。\n",
    "\n",
    "## 队列抽象数据类型\n",
    "队列抽象数据类型由以下结构和操作定义。如上所述，队列被构造为在队尾添加项的有序集合，并且从队首移除。队列保持 FIFO 排序属性。 队列操作如下。\n",
    "- Queue() 创建一个空的新队列。 它不需要参数，并返回一个空队列。\n",
    "- enqueue(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。\n",
    "- dequeue() 从队首移除项。它不需要参数并返回 item。 队列被修改。\n",
    "- isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。\n",
    "- size() 返回队列中的项数。它不需要参数，并返回一个整数。\n",
    "\n",
    "作为示例，我们假设 q 是已经创建并且当前为空的队列，则 Table 1 展示了队列操作序列的结果。右边表示队首。 4 是第一个入队的项，因此它 dequeue 返回的第一个项。\n",
    "\n",
    "*Table 1 队列抽象数据类型.*\n",
    "![](figures/3.11.table1.png)\n",
    "\n",
    "## Python实现队列\n",
    "我们为了实现队列抽象数据类型创建一个新类。\n",
    "\n",
    "我们需要确定列表的哪一端作为队首，哪一端作为队尾。\n",
    "下面的代码所示的实现假定队尾在列表中的位置为 0。这允许我们使用列表上的插入函数向队尾添加新元素。弹出操作可用于删除队首的元素（列表的最后一个元素）。\n",
    "\n",
    "回想一下，这也意味着入队复杂度为 O(n)，出队为 O(1)。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def enqueue(self, item):\n",
    "        self.items.insert(0, item)\n",
    "\n",
    "    def dequeue(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "进一步的操作这个队列产生如下结果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<__main__.Queue object at 0x0000025FE389E040>\n",
      "True\n",
      "False\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "a = Queue()\n",
    "print(a)\n",
    "\n",
    "print(a.isEmpty())\n",
    "a.enqueue(1)\n",
    "print(a.isEmpty())\n",
    "print(a.dequeue())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bill\n",
      "Susan\n",
      "Brad\n",
      "David\n",
      "Jane\n",
      "Kent\n"
     ]
    }
   ],
   "source": [
    "def hotPotato(namelist, num):\n",
    "    simqueue = Queue()\n",
    "    for name in namelist:\n",
    "        simqueue.enqueue(name)\n",
    "\n",
    "    while simqueue.size() > 1:\n",
    "        for i in range(num):\n",
    "            simqueue.enqueue(simqueue.dequeue())\n",
    "\n",
    "        print(simqueue.dequeue())\n",
    "\n",
    "    return simqueue.dequeue()\n",
    "\n",
    "print(hotPotato([\"Bill\", \"David\", \"Susan\", \"Jane\", \"Kent\", \"Brad\"], 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Printer:\n",
    "    def __init__(self, ppm):\n",
    "        self.pagerate = ppm\n",
    "        self.currentTask = None\n",
    "        self.timeRemaining = 0\n",
    "\n",
    "    def tick(self):\n",
    "        if self.currentTask != None:\n",
    "            self.timeRemaining = self.timeRemaining - 1\n",
    "            if self.timeRemaining <= 0:\n",
    "                self.currentTask = None\n",
    "\n",
    "    def busy(self):\n",
    "        if self.currentTask != None:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def startNext(self, newtask):\n",
    "        self.currentTask = newtask\n",
    "        self.timeRemaining = newtask.getPages() * 60/self.pagerate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "class Task:\n",
    "    def __init__(self, time):\n",
    "        self.timestamp = time\n",
    "        self.pages = random.randrange(1, 21)\n",
    "\n",
    "    def getStamp(self):\n",
    "        return self.timestamp\n",
    "\n",
    "    def getPages(self):\n",
    "        return self.pages\n",
    "\n",
    "    def waitTime(self, currenttime):\n",
    "        return currenttime - self.timestamp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average Wait  32.73 secs   0 tasks remaining.\n",
      "Average Wait   5.95 secs   0 tasks remaining.\n",
      "Average Wait  12.10 secs   0 tasks remaining.\n",
      "Average Wait  20.53 secs   0 tasks remaining.\n",
      "Average Wait  92.00 secs   0 tasks remaining.\n",
      "Average Wait  17.53 secs   0 tasks remaining.\n",
      "Average Wait   9.54 secs   0 tasks remaining.\n",
      "Average Wait  11.05 secs   0 tasks remaining.\n",
      "Average Wait  29.65 secs   0 tasks remaining.\n",
      "Average Wait  18.23 secs   0 tasks remaining.\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.queue import Queue\n",
    "\n",
    "import random\n",
    "\n",
    "def simulation(numSeconds, pagesPerMinute):\n",
    "\n",
    "    labprinter = Printer(pagesPerMinute)\n",
    "    printQueue = Queue()\n",
    "    waitingtimes = []\n",
    "\n",
    "    for currentSecond in range(numSeconds):\n",
    "        if newPrintTask():\n",
    "            task = Task(currentSecond)\n",
    "            printQueue.enqueue(task)\n",
    "\n",
    "        if (not labprinter.busy()) and (not printQueue.isEmpty()):\n",
    "            nexttask = printQueue.dequeue()\n",
    "            waitingtimes.append(nexttask.waitTime(currentSecond))\n",
    "            labprinter.startNext(nexttask)\n",
    "        else:\n",
    "            labprinter.tick()\n",
    "\n",
    "    averageWait = sum(waitingtimes) / len(waitingtimes)\n",
    "    # print(waitingtimes)\n",
    "    print(\"Average Wait %6.2f secs %3d tasks remaining.\" %\n",
    "          (averageWait, printQueue.size()))\n",
    "\n",
    "def newPrintTask():\n",
    "    num = random.randrange(1, 181)\n",
    "    if num == 180:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "# simulation(3600, 5)\n",
    "\n",
    "for i in range(10):\n",
    "    simulation(3600, 10)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0ba00dd77806596ecbc07d55b4ddf41b2ae8cecbf91d9534027e74a33368b668"
  },
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit ('base': conda)",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
